Logic and Knowledge Representation

Proposition

A proposition is a statement that can be true or false, in other words, a variable taking value in $\lbrace 0,1\rbrace $

Inductive Learning

Observe some configuration from $D$
conclude some property such as $C$

Note, the unobserved worlds may violate the inferred property. Only tautologies (true in all possible worlds) can be known to be true from pure observation alone.

Example: Proposition & Inductive Learning

A layout with a hallway and two rooms (room 1/2)

A robot and a box can be in any of these places.

Thus, we can have a set of propositions, each of which represents an item in a specific location

Proposition (e.g.)

$X_1$ the robot is in the hallway

$X_2$ the robot is in room 1

$X_3$ the robot is in room 2

$X_4$ the box is in the hallway

$X_5$ the box is in room 1

$X_6$ the box is in room 2

$X_7$ the robot is holding the box

Then we have a set of all possible worlds $\lbrace 0,1\rbrace ^7$

Set of actual possibilities $D\in \lbrace 0,1\rbrace ^7$

Property (e.g.)

Robot + box occupy one place at any time

If the robot is holding the box, they are in the same place

etc.

each is a property—can define each by the sets of pass worlds where the properties hold

e.g., properpty ”robot is in the exactly one place” = $\lbrace (1,0,0),(0,1,0),(0,0,1)\rbrace \times \lbrace 0,1\rbrace ^4$

$C$ is valid for $D$ $\iff$ $D\subseteq C$

After observing a couple of examples, we declare “the robot is in exactly one place”

If $C\not\in \lbrace 0,1\rbrace ^7$ (see of all possible worlds) and we dont observe every assignment in $D$, $D$ could contain a world which $C$ is false.

Only tautologies (true in all possible worlds) can be known to be true

Consider states $X_{i,pre}$ (before action), $X_{i,post}$ (after action)

A rule that should hold: if (”the robot is holding the box” $\land$ “ends in room 1”) then “the box should also end in room 1”

We can write the implication “if A then B” as $(\lnot A)\lor B$

So by the De Morgan’s Law, we can write the rule as $\lnot$ “the robot is holding the box” $\lor\lnot$ “ends in room 1” $\lor$ “the box ends in room 1”

Knowledge Representation

A knowledge representation is a partial mapping from strings over an alphabet $\Sigma$ to sets of possible worlds (properties)

Expressability

Truth table, databases (All properties)
Most expressive: DNF; Due to Tribes
Decision Tree; can describe $x_1\oplus x_2$
Least: Conjunctions and Disjunctions (their union is the literals)

De Morgan Formulas

De Morgan formulas are defined using a set of propositional attributes $X_i$ and the connectives $\land$ (and), $\lor$ (or), and $\lnot$ (not).

Attributes are De Morgan formulas
For any formla $\psi$, $\lnot\psi$ is a formula
For formula $\phi$ and $\psi$, $\phi\land\psi$ and $\phi\lor\psi$ are formulas

Database Representation

List assignments satisfying the proposition

Truth table representation

On $n$ Boolean attributes, a string of length $2^n$ st. $i$-th symbol indicates if $i$-th setting satisfy the property

Conjunctions

Conjunctions are the following family of Boolean formulas

for any attributes $X_i$ or $\lnot X_i$ is conjunction
For any conjunctions $\phi$ and $\psi$, $\phi\land\psi$ is a conjunction

Disjunctions

for any attributes $X_i$ or $\lnot X_i$ is disjunction
For any conjunctions $\phi$ and $\psi$, $\phi\lor\psi$ is a disjunction

Decision Tree

A decision tree is a rooted binary tree

Each internal node is labeled with an attribute $X_i$
The two outgoing edges are labeled with truth values 0 and 1.
Leaves are labeled with output truth values.

Given a possible world, starting at the root, read the value of the attribute on the node, take the corresponding edge, and repeat until a leaf. The leaf gives the truth value.

Disjunctive Normal Forms (DNF) formulas

Any conjunction is a DNF
Any DNFs $\phi$ and $\psi$, then $\phi\lor\psi$ is a DNF

More expressive than a decision tree because of “Tribes”

This can represent all possibilities, since:

For every possible world $\bar x\in \lbrace 0,1\rbrace ^n$ there is a conjunction representing $\lbrace \bar x\rbrace $.

The conjunction has the literal $x_i$ if $x_i=1$ otherwise it has $\lnot x_i$

Thus, $\bar x$ satisfies the conjunction (the conjunction is true of $\bar x$)

Any $\bar x'$ that satisfies the conjunction agrees with $\bar x$ in all attributes, so $\bar x'=\bar x$
For any property $c$, consider DNF, $\bigvee_{\bar x\in C} c_{\bar x}$.

This will satisfy if and only if one of the $c_{\bar x}$ for $\bar x\in C$ are satisfied, if and only if $\bar x\in C$

There does not exist a representation that is small (reasonable size) for all possible properties.

Knowledge representation maps strings over $\Sigma$ to subsets of the possible worlds.

There cannot exist a set of short strings such that every subset of the possible world is corresponence with a unique string.

Suppose the strings have length $\leq\ell$.

Thus, there are $2^{\ell+1}-1$ strings with length $\leq\ell$

There are $2^{2^n}$ properties on $n$ Boolean attributes.

Thus, we need $2^{\ell+1}-1\geq 2^{2^n}\iff \ell+1>2^n$

Decision Tree to DNF

Any decision tree of size $s$ on $n$ attributes can be written by a DNF of size $\leq O(ns)$

For each leaf giving value $1$, there is a conjunction that is true on exactly the possible worlds that take that path to that leaf. That conjunction uses at most $n$ literals.

The decision tree maps a possible world to 1 if and only if it reaches one of the label-1 leaves.

$\bigvee_{\text{leafs of tree}} [\text{leaf-path conjunction}]$ (a DNF)

This can be satisfied for precisely the possible worlds that satisfy the conjunctions for one of the tree’s leaf. If and only if, the the tree labels the possible world is 1.

Thus, the DNF has size $O(sn)$

DNF to Decision Tree

The following family of DNFs of size $s$ require decision trees of size $2^{\Omega(s)}$.

Example: Not representable as a disjunction

Suppose for contradiction that some disjunction could represent $X_1\land X_2$. Suppose so.

Then it must be false whenever $X_1$ is true but $X_1\land X_2$ is false, so the disjunction cannot contain $X_1$. Similarly, it must be false whenever $X_1$ is false but $X_1\land X_2$ is false, so the disjunction cannot contain $\lnot X_1$.But then the value of the disjunction foes not depend on $X_1$, os it takes the same value in the world where ( $X_1=1$ and $X_2=1$ ) and ( $X_1=0$ and $X_2=1$ ) but $X_1\land X_2$ takes different values in these.

$X_1\oplus X_2$, which is exactly one of $X_1$ and $X_2$ is true, can’t be represented either

De Morgan’s Law

$\lnot[\psi\land\phi]=(\lnot\psi)\lor(\lnot\phi)$

$\lnot[\psi\lor\phi]=(\lnot\psi)\land(\lnot\phi)$